1. Field of the Invention
The present invention relates to a packet relay apparatus configured to relay a packet and a method of relaying a packet.
2. Description of the Related Art
Extremely heavier communication traffic or an excess communication request significantly exceeding the capacity of a communication relay apparatus may interfere with smooth communication. This is generally called congestion of communication. The congestion occurs in any communication including the today's Internet communication.
The Internet communication generally receives and sends data in units of packets. Switches and routers are typical examples of packet relay apparatuses configured to relay such packets. The packet relay apparatus generally has queues for temporary storage of packets. Each queue works to restrict the occurrence of packet drop in the burst traffic caused by an overlapped arrival of multiple packets between plural flows in communication of the packet relay apparatus. The queue also serves for packet priority control and communication band control to actualize the QoS (Quality of Service).
The communication traffic over the acceptable range of the packet relay apparatus may cause congestion. A network of the Internet basically adopts the best effort network communication scheme. In a typical protocol TCP/IP (Transmission Control Protocol/Internet Protocol) used in the Internet, a packet retransmission scheme between terminals of packet reception and transmission is implemented to maintain the integrity of communication even in data propagation over a quality-unguaranteed network. The packet relay apparatus used on the Internet is subject to packet drop control in order to assure the low-cost and high-speed communication. This packet drop control is of extreme importance.
Tail Drop and RED (Random Early Detection) are typical queue management algorithms for the packet drop control. The Tail Drop algorithm uses a maximum threshold value representing the maximum packet storage capacity set in each queue. When a queue length of a certain queue exceeds its maximum threshold value, the Tail Drop algorithm drops overflowed packets from the certain queue. This control scheme is readily implemented but causes a slow start of packet retransmission by simultaneous packet drop and gives only a poorer throughput than expected under TCP/IP communication.
The other typical algorithm RED uses a minimum threshold value, a maximum threshold value, and a maximum packet drop rate as parameters set in each queue. When a queue length of a certain queue exceeds its minimum threshold value, the RED algorithm drops packets with a drop probability corresponding to the queue length. The incoming packets are gradually dropped with the drop probability corresponding to the queue length until the queue length reaches its maximum threshold value. When the queue length reaches or exceeds the maximum threshold value, packets are overflowed from the certain queue, so that all the overflowed packets are dropped. The RED algorithm has more difficulty in implementation than the Tail Drop algorithm but allows packets to be gradually dropped at a rate corresponding to the queue length. This control scheme avoids the phenomenon of simultaneous packet retransmission under TCP/IP communication and assures execution of the original line performance.
There are some variants proposed for these two packet drop control algorithms, i.e., WTD (Weighted Tail Drop) and WRED (Weighted Random Early Detection). Both the variant algorithms adopt different policies for different applications of packets and set different drop threshold values for the different applications to achieve packet drop control with different priorities. The WTD algorithm sets different maximum threshold values of queue length for different applications of packets. The WRED algorithm sets different minimum threshold values, different maximum threshold values, and different maximum packet drop rates for different applications of packets. Both these variant control schemes are highly functional to enable packet drop control with different priorities set for the respective applications of packets but require rather complicated information management with regard to the respective applications.
Some packet relay apparatuses adopt a multi-stage queue structure. In the packet relay apparatuses adopting the multi-stage queue structure, the maximum queue length of each queue may be designed on the concept of statistical multiplexing effect. The ‘statistical multiplexing effect’ sets an overall queue length that is less than the sum of the maximum capacities of queue length of respective queues, on the assumption that it is unlikely that all the queues simultaneously have queue lengths filled to their maximum capacities. The scheme without the concept of statistical multiplexing effect requires the memory capacity corresponding to the sum of the maximum capacities of queue length of the respective queues. The scheme on the concept of statistical multiplexing effect, on the other hand, requires a smaller memory capacity, thus attaining the resource saving and reducing the cost and power consumption.
In the multi-stage queue structure of the packet relay apparatus designed on the concept of the statistical multiplexing effect, the maximum length of a queue monitoring the overall buffer memory capacity is shorter than the sum of the maximum capacities of queue length of all queues at a former stage. In this internal configuration, congestion of a queue at the former stage may cause the queue monitoring the overall buffer memory capacity may be overflowed first. For example, in a simple scheme of storing packets in a queue (queuing) if there is still room to the overall buffer memory capacity, accumulation of packets in a specific queue may lead to a packet overflow of a queue at a latter stage. This restrains other queues from using the buffer memory and thereby interferes with smooth communication of the other queues. This is generally recognized as occupancy of the buffer memory by the specific queue.
A technique disclosed in, for example, JPH10-173661A has been proposed to address this issue. When the queue length of the queue monitoring the overall buffer memory capacity exceeds a predetermined rate, this proposed technique shifts the state and performs control to shorten the maximum threshold values of queue length of all the queues by a fixed rate. This shortens the threshold values of the respective queues by a fixed rate. A notice of congestion is sent to a sender connected to a certain queue having a longer queue length than its shortened threshold value. The sender receiving the notice of congestion lowers the communication speed to decrease the number of packets accumulated in the certain queue from the buffer memory. This eliminates the occupancy of the buffer memory by the certain queue and enables the other users to make communication.
The technique disclosed in JPH10-173661A has not, however, been developed on the premise of the today's Internet communication and accordingly has the following operations in application to the Internet-based packet communication. When the threshold values of the respective queues are shortened by a fixed rate, a certain queue with accumulation of a greater number of packets than its shortened threshold value simultaneously drops all incoming packets exceeding the threshold value. The other users failing to make communication by the occupancy of the buffer memory by the certain queue in the communication band are then allowed to make communication.
The user connected to the certain queue having the queue length over its shortened threshold value is, on the other hand, forced to perform simultaneous retransmission of all the dropped packets on a slow start. This significantly lowers the overall throughput of the network. The technique disclosed in JPH10-173661A starts a series of processing in response to detection of congestion of the queue monitoring the overall buffer memory capacity. It is thus highly probable that congestion simultaneously affects all the queues and causes packets to be simultaneously dropped from all the queues. This technique does not actualize flexible drop control for the users having different priorities.
These issues are not restricted to the packet relay apparatuses designed on the concept of the statistical multiplexing effect but are commonly found in diversity of packet relay apparatuses utilizing the multi-stage queue structure.